package com.code.leetcode.offer;

/**
 * @author codeDorado
 * @version 1.0
 * @date 2020/8/2 17:05
 */
public class The42_dp {
    public int maxSubArray(int[] nums) {
        int temp = nums[0];
        for (int i = 1; i < nums.length; i++) {
            nums[i] += Math.max(nums[i - 1], 0);
            temp = Math.max(temp, nums[i]);
        }
        return temp;
    }

    public static void main(String[] args) {
        The42_dp the42 = new The42_dp();
        System.out.println(the42.maxSubArray(new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4}));
    }
}
